﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    /*
     * 
     * The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.
*/
    class Problem60 : IProblem
    {
        SieveOfAtkin sieve;

        public string Calculate()
        {


            DateTime before = DateTime.Now;
            sieve = new SieveOfAtkin(100000000);
            DateTime after = DateTime.Now;

            TimeSpan totalTime = after.Subtract(before);
            Console.WriteLine("Sieve time {0}h {1}m {2}s {3}ms", totalTime.Hours, totalTime.Minutes, totalTime.Seconds, totalTime.Milliseconds.ToString("000"));

            long minSum = 30785; //259 397 907 3919 4567

            for (long i = 3; i < minSum / 5; i += 2)
            {
                if (sieve.IsPrime(i))
                {
                    List<long> primes = new List<long>() { i, i };
                    minSum = MinimumSum(primes, 5, minSum);
                }
            }
            Console.Beep(2000, 100);

            return minSum.ToString();
        }

        long MinimumSum(List<long> primes, int limit, long minSum)
        {
            while (true)
            {
                primes[primes.Count - 1] += 2;

                if (primes.Count == limit)
                {
                    if (primes.Sum() > minSum)
                        return minSum;
                }
                else
                {
                    long sum = primes.Sum();
                    sum += primes[primes.Count - 1] * (limit - primes.Count);
                    if (sum > minSum)
                        return minSum;
                }
                if (sieve.IsPrime(primes[primes.Count - 1]))
                    if (ArePermutationsPrime(primes))
                    {
                        if (primes.Count < limit)
                        {
                            List<long> newList = new List<long>(primes);
                            newList.Add(primes[primes.Count - 1]);
                            minSum = MinimumSum(newList, limit, minSum);
                        }
                        else
                        {
                            Console.WriteLine(primes.Sum());
                            for (int i = 0; i < primes.Count; i++)
                                Console.Write(primes[i] + " ");
                            Console.WriteLine();
                            return primes.Sum();
                        }
                    }
            }
        }

        bool ArePermutationsPrime(List<long> primes)
        {
            if (primes.Count < 2)
                throw new ArgumentException();

            long concatenation = 0;
            int k = 2;
            concatenation = primes[1] + primes[0] * (int)Math.Pow(10, CommonFunctions.NumberOfDigits(primes[1]));


            if (!sieve.IsPrime(concatenation))
                return false;

            List<int> pickingOrder = new List<int>();
            for (int i = 0; i < k; i++)
                pickingOrder.Add(0);


            while (true)
            {
                bool finished = true;
                for (int i = 0; i < pickingOrder.Count; i++)
                    if (pickingOrder[i] != primes.Count - 1 - i)
                        finished = false; //picking order je za primjer 9, 8, 7, 6

                if (finished)
                    break;

                int overflow = 1;
                int target = pickingOrder.Count;

                //gledamo gdje cemo dodat jedan
                while (overflow == 1 && target >= 0)
                {
                    target--; //prvi put je na kraj (pickingOrder.Count - 1)
                    pickingOrder[target]++; //povecamo za jedan              
                    if (pickingOrder[target] >= (pickingOrder.Count - target) + (primes.Count - k)) //ako je prekoracilo
                    {
                        for (int i = target; i < pickingOrder.Count; i++)
                        {
                            pickingOrder[i] = 0; //vratimo ostale na nulu
                        }
                    }
                    else
                    {
                        overflow = 0; //nije prekoracilo
                    }
                }

                List<long> tempCharacterList = new List<long>(primes);
                concatenation = 0;
                for (int i = 0; i < pickingOrder.Count; i++)
                {
                    concatenation *= (int)Math.Pow(10, CommonFunctions.NumberOfDigits(tempCharacterList[pickingOrder[i]]));
                    concatenation += tempCharacterList[pickingOrder[i]]; ;
                    tempCharacterList.RemoveAt(pickingOrder[i]);
                }
                if (!sieve.IsPrime(concatenation))
                    return false;
            }
            return true;
        }
    }
}
